# -*- encoding: utf-8 -*-

"""
------------------------------------------
@File       : 13_get_gcd.py
@Author     : maixiaochai
@Email      : maixiaochai@outlook.com
@CreatedOn  : 2022/1/26 16:10
------------------------------------------
    求两个整数的最大公约数
    Tips：
        1) 辗转相除法（欧几里得算法）:
           两个正整数 a和 b (a > b)，它们的最大公约数等于 a除以 b得到的余数 c 和 b 之间的最大公约数。
           例如，25 和 10，25 除以 10商 2余 5，那么 25 和 10的最大公约数，等于 5和 10的最大公约数

           利用这个方法，采用递归的方式，逐渐把两个较大整数之间的运算简化成两个较小整数之间的运算，
           直到两个数可以整除，或者其中一个数减小到 1为止

           但是，当两个数相差较大时，a % b 的性能较差

        2) 用 更相减损术 进一步优化算法
           更相减损术出自《九章算术》，也是一种求最大公约数的算法。
           两个正整数 a和 b (a > b)，它们的最大公约数等于 a - b 的差值 c和较小数 b的最大公约数。
           例如，25和 10，25 - 10 = 15，则 25和 10的最大公约数，等价于 15和 10的最大公约数

           用递归或栈的方式，逐步把两个较大的整数之间的运算简化成两个较小整数之间的运算。直到两个数相等为止。
           最大公约数就是最终相等的这两个数的值

       3) 结合 1)和 2)的优势，更进一步的性能优化，在 2)的基础上使用位移运算
"""


def get_greatest_common_divisor_v1(a, b):
    """
        辗转相除法，求最大公约数
    """
    big = max(a, b)
    small = min(a, b)

    if big % small == 0 or small == 1:
        return small

    return get_greatest_common_divisor_v1(big % small, small)


def get_greatest_common_divisor_v2(a, b):
    """
        更相减损术
        缺点：当两数相差悬殊时，如计算 10000和 1的最大公约数，就要递归 9999次
    """
    if a == b:
        return a

    big = max(a, b)
    small = min(a, b)

    return get_greatest_common_divisor_v2(big - small, small)


def gcd(a, b):
    """
        结合 1)和 2)的优势，更进一步的性能优化，在 2)的基础上使用位移运算(更相减损法上)，进一步优化性能。
        使用位移，位移的性能非常高

        当 a和 b均为偶数时，gcd(a, b) = 2 X gcd(a/2, b/2) = 2 X gcd(a>>1, b>>1)
        当 a为偶数，b为奇数时，gcd(a, b) = gcd(a/2, b) = gcd(a>>1, b)
        当 a为奇数，b为偶数时，gcd(a, b) = gcd(a, b/2) = gcd(a, b>>1)
        当 a, b均为奇数时，先利用更相减损术运算一次，gcd(a, b) = gcd(b, a - b)，此时，a -b 必然是偶数，然后又可以继续进行位移运算
    """
    if a == b:
        return a

    # (a & 1) == 0 说明整数 a是偶数，(a & 1 ) != 0 说明整数 a是奇数
    # 一个偶数右移，则/2;
    # 一个数（无论奇数还是偶数）左移，x 2
    if (a & 1) == 0 and (b & 1) == 0:
        return gcd(a >> 1, b >> 1) << 1

    if (a & 1) == 0 and (b & 1) != 0:
        return gcd(a >> 1, b)

    if (a & 1) != 0 and (b & 1) == 0:
        return gcd(a, b >> 1)

    else:
        big = max(a, b)
        small = min(a, b)

        return gcd(big - small, small)


def demo():
    a, b = 100, 30
    # print(get_greatest_common_divisor_v2(a, b))
    print(gcd(a, b))


if __name__ == '__main__':
    demo()
